# 考点：DFS
"""
题目描述
给一个无向图染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色，输出有多少种不同的染色方案？

输入描述
第一行输入M(图中节点数) N(边数)

后续N行格式为：V1 V2表示一个V1到V2的边。

数据范围：1 <= M <= 15,0 <= N <= M * 3，不能保证所有节点都是连通的。

说明
0 < n < 15
0 <= m <= n * 3
0 <= s, t < n
不保证图连通
保证没有重边和自环

输出描述
输出一个数字表示染色方案的个数。

示例1
输入

4 4
1 2
2 4
3 4
1 3

输出

7

说明

4个节点，4条边，1号节点和2号节点相连，
2号节点和4号节点相连，3号节点和4号节点相连，
1号节点和3号节点相连，
若想必须保证相邻两个节点不能同时为红色，总共7种方案。

示例2
输入

3 3
1 2
1 3
2 3

输出

4

说明

解题思路
要解决这个图的染色问题，我们可以利用深度优先搜索（DFS）进行递归遍历每一个节点，对于每个节点，我们可以选择将其染为红色或黑色，同时要注意相邻节点的限制条件。

步骤分析:
输入处理：
读取节点数 M 和边数 N。然后将接下来的 N 行表示为无向边存储在一个二维布尔数组中, 这个数组可以表示图的邻接矩阵。

DFS 递归函数设计：

定义一个递归函数 dfs，它接受当前节点索引、上次染红的节点（通过位运算表示），以及图的邻接矩阵作为参数。
如果当前节点的索引超过 M，说明染色完成，返回1（表示成功的一种方案）。
染色决策：

染黑色: 在每次调用 DFS 时，首先尝试将当前节点染色为黑色，不需要进行任何检查，直接继续到下一个节点。
染红色: 对于染红色的情况，需要检查当前节点的邻接节点是否已经被染为红色。通过位运算判断当前节点的邻接节点的状态。
通过检查邻接矩阵和红色节点的状态，确定当前节点是否可以染红。
如果可以染红，将其状态更新，调用 recursively 继续下一节点。
"""

'''
题解
题目类型：
这道题目属于 位运算 和 枚举 类型的题目，结合了图的染色问题，主要通过枚举所有可能的染色方案来判断是否满足约束条件。
解题思路：
	题目理解： 
	给定一个无向图，图中的每个节点要么是红色，要么是黑色，且相邻的两个节点不能同时为红色。
	需要计算出图中满足染色条件的所有方案的个数。
	枚举所有可能的染色方案： 
	假设有 m 个节点，那么可以用一个二进制数表示所有节点的颜色方案。 
	二进制数的每一位表示一个节点的颜色（0 为黑色，1 为红色）。
	例如，对于 m = 3，染色方案可以是： 
	000（黑色、黑色、黑色）
	001（黑色、黑色、红色）
	010（黑色、红色、黑色）
	111（红色、红色、红色）等。
	检查染色是否合法： 
	对于每一个染色方案，检查是否满足相邻节点不能同时为红色的约束。
	如果满足条件，则增加计数。
	算法实现： 
	使用一个二进制数表示每一个染色方案，遍历从 0 到 2^m - 1 的所有可能的方案。
	对每一个染色方案，通过位运算提取节点的颜色，检查相邻节点的颜色是否满足条件。
代码大致描述：
	输入： 
	输入包括节点数 m 和边数 n，接着输入 n 条边，每条边表示一对相邻的节点。
	检查染色方案的有效性： 
	对于每个染色方案，检查相邻的节点是否满足约束：即相邻两个节点不能同时为红色（即二进制表示中对应位不能同时为1）。
	输出： 
	输出符合要求的染色方案的个数。
时间复杂度：
	时间复杂度：
	我们枚举所有的染色方案，染色方案的总数为 2^m（即 1 << m）。
	对于每一个染色方案，我们需要检查所有的边（即 n 条边），对于每条边，需要进行常数时间的操作（位运算）。因此，时间复杂度为： O(2^m×n)
	由于 m 最大为 15，因此 2^m 最多为 32768，n 最大为 m * 3 = 45，所以时间复杂度在最坏情况下是 O(2^m×n)，即最多约为 1.5 million 次操作，足够在合理时间内完成。
	空间复杂度：
	存储图的边需要 O(n) 的空间。
	存储染色方案和结果需要 O(1) 空间，除去输入和输出。
	因此，空间复杂度是 O(n)。


作者：优秀的仰泳鲈鱼在对齐目标
链接：https://www.nowcoder.com/discuss/742766442340237312?sourceSSR=search
来源：牛客网
'''


'''
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    if not data:
        print(0)
        return
    
    M = int(data[0])
    N = int(data[1])
    
    edges = []
    idx = 2
    for i in range(N):
        u = int(data[idx]) - 1  # 转为0-based
        v = int(data[idx + 1]) - 1
        idx += 2
        edges.append((u, v))
    
    total = 0
    # 枚举所有可能的红色节点集合（mask）
    for mask in range(1 << M):
        valid = True
        for u, v in edges:
            # 如果u和v都是红色（对应位都是1），则非法
            if (mask >> u) & 1 and (mask >> v) & 1:
                valid = False
                break
        if valid:
            total += 1
            
    print(total)

if __name__ == "__main__":
    main()
'''


def main():
    import sys
    input = sys.stdin.readline  # 更高效

    first_line = input().split()
    if not first_line:
        print(0)
        return

    M = int(first_line[0])
    N = int(first_line[1])

    edges = []
    for _ in range(N):
        u, v = map(int, input().split())
        edges.append((u - 1, v - 1))  # 转为0-based

    total = 0
    for mask in range(1 << M):
        ok = True
        for u, v in edges:
            if (mask >> u) & 1 and (mask >> v) & 1:
                ok = False
                break
        if ok:
            total += 1

    print(total)


if __name__ == "__main__":
    main()